每个数的数字和的和其实就是所有数字与它出现次数的积的和。
那么对于 ，依次像 P2602 [ZJOI2010]数字计数 统计出现次数就可以了。
具体做法也很简单，记录前 位某个数字出现次数 ，记忆化搜索即可通过。
最后附上双倍经验：P4999 烦人的数学作业
#include <cstdio>
#include <cstring>
#define int long long
const int MAXN = 15;
int a[ MAXN + 5 ] , len , dp[ MAXN + 5 ][ MAXN + 5 ];
int dfs( int pos , int lead , int limit , int sum , int digt ) {
if( pos == len + 1 ) return sum;
if( ~dp[ pos ][ sum ] && !lead && !limit ) return dp[ pos ][ sum ];
int Ans = 0 , Mbit = limit ? a[ len - pos + 1 ] : 9;
for( int i = 0 ; i <= Mbit ; i ++ ) {
if( lead && i == 0 ) Ans += dfs( pos + 1 , 1 , limit & ( i == Mbit ) , sum , digt );
else Ans += dfs( pos + 1 , 0 , limit & ( i == Mbit ) , sum + ( i == digt ) , digt );
}
if( !lead && !limit ) dp[ pos ][ sum ] = Ans;
return Ans;
}
int Solve( int digt , int x ) {
if( x < 0 ) return 0;
len = 0; for( ; x ; x /= 10 ) a[ ++ len ] = x % 10;
memset( dp , -1 , sizeof( dp ) );
return dfs( 1 , 1 , 1 , 0 , digt );
}
int t , l , r , Ans;
signed main( ) {
scanf("%lld",&t);
while( t -- ) {
scanf("%lld %lld",&l,&r);
Ans = 0;
for( int i = 0 ; i <= 9 ; i ++ ) Ans += i * ( Solve( i , r ) - Solve( i , l - 1 ) );
printf("%lld\n", Ans );
}
return 0;
}
